连通图的最大生成树的权和

2017-07-31 Algorithm 阅读量

这是一道Google 笔试题

题目

一个有n个结点的连通图的生成树是原图的最小连通子图, 且包含原图中所有n个结点，并且有保持图联通的最少的边。最大生成树就是权和最大生成树，现在给出一个无向带权图的邻接矩阵，权为0表示没有边。

{{0, 4, 5, 0, 3}, 
 {4, 0, 4, 2, 3}, 
 {5, 4, 0, 2, 0}, 
 {0, 2, 2, 0, 1}, 
 {3, 3, 0, 1, 0}}

求这个图的最大生成树的权和。

A、11

B、12

C、13

D、14

E、15

分析

题意是在考察最大生成树，我们需要根据给出的邻接矩阵代表的无向带权图求出最大生成树，然后计算权和就很简单水到渠成了。

最小生成树

说到最大生成树，我们得先回顾一下最小生成树：

最小生成树其实是最小权重生成树的简称。一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。也就是说最小生成树就是边权重之和最小的生成树。总结起来就是以下：

1）必须使用且仅使用该网络中的n-1条边来连接网络中的n个顶点。
2）不能使用产生回路的边。
3）各边上的权值的总和达到最小。

简单点说有几个城市你要设计一个路线，这个路线能走完所有的这几个城市，而且路程最短，这个路线就是最小生成树的含义。相反地，最大生成树就是边权重之和最大的生成树。

那么，如何生成最小生成树呢？常用的算法有Prim算法（普里姆算法）和Kruskal算法（克鲁斯克尔算法）。

Prim算法

Prim算法是用来从带权图中搜索最小生成树的一种算法。从单一顶点开始，Prim普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

输入：一个加权连通图，其中顶点集合为$V$ ，边集合为$E$；
初始化：$V_{new} = {x}$ ，其中x为集合V中的任一节点（起始点）， $E_{new} = \{\}$ ；
重复下列操作，直到$V_{new} = V$ ：

a. 在集合E中选取权值最小的边（u, v），其中u为集合$V_{new}$中的元素，而v则是V中没有加入$V_{new}$的顶点（如b. 果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；将v加入集合$V_{new}$中，将（u, v）加入集合$E_{new}$中；
输出：使用集合$V_{new}$和$E_{new}$来描述所得到的最小生成树。

算法伪代码：

Prim(G, T) {
    T = NULL;
    U = {w};    //添加任一顶点w
    while((V - U)!=NULL) {
        设(u, v)是u ∈ U 与 v ∈ （V - U),且权值最小的边
        T = T ∪ (u, v);
        U = U ∪ v ;
    }
}

说白了，就是将起点u（任一节点）放入空集合S，则S = {u}；再找到距离集合S最近的一点u，加入S集合。直到所有节点都加入进来。

Prim算法时间复杂度为O(V^2)，比较适合于求稠密图的最小生成树。

Kruskal算法

Kruskal算法是一种按权值的递增次序选择合适的边来构成最小生成树的方法。算法描述如下：

新建图G，G中拥有原图中相同的节点，但没有边
将原图中所有的边按权值从小到大排序
从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中
重复3，直至图G中所有的节点都在同一个连通分量中

算法伪代码：

KRUSKAL-FUNCTION(G, w)
    F := 空集合
    for each 图 G 中的顶点 v
        do 將 v 加入森林 F
    所有的边(u, v) ∈ E依权重 w 递增排序
   for each 边(u, v) ∈ E
        do if u 和 v 不在同一棵子树
            then F := F ∪ {(u, v)}
                將 u 和 v 所在的子树合并

小结

Prim算法：是针对顶点展开的，适合于边数较多的情况。

Kruskal算法：是针对边展开的，适合于边的数量较少的情况。

解决

使用Krustal算法或者Prime算法构造“”最大生成树”：

Prime算法：选择权重最大的边的两个顶点加入等价类
Krustal算法：即每次选择权重最大的边加入森林；

我们看邻接矩阵

	A	B	C	D	E
A	0	4	5	0	3
B	4	0	4	2	3
C	5	4	0	2	0
D	0	2	2	0	1
E	3	3	0	1	0

利用Krustal算法，选择最大的边加入，但是不能形成回路，图中表黑的就是被选出的，DE边是不能选的，否则就形成闭路。总共5+4+3+2=14

题目

分析

最小生成树

Prim算法

Kruskal算法

小结

解决

参考资料